package com.acyouzi.leetcode.dp;

/**
 * 17/9/16 10:04
 *
 * @author sunxu
 */
public class NumberLongestIncreasingSubsequence {
  // 注意这里首先要求最长，然后才是求数量
  public int findNumberOfLIS(int[] nums) {
    int n = nums.length;
    int[] len = new int[n];
    int[] cnt = new int[n];
    int max = 0;
    for(int i = 0; i<n; i++){
      len[i] = 1;
      cnt[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]){
          // 如果当前位置长度等于需要累加的位置 + 1，说明长度相同，累加，这一步很重要
          if(len[i] == len[j] + 1)cnt[i] += cnt[j];
          // 否则说明 len[i] 不是最长的,替换为最长的
          if(len[i] < len[j] + 1){
            len[i] = len[j] + 1;
            cnt[i] = cnt[j];
          }
        }
      }
      max = Math.max(max,len[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      if (max == len[i]) res += cnt[i];
    }
    return res;
  }
}
